#include "heap_sort.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

tree_node_t *new_tree_node(int data){
    tree_node_t *node = malloc(sizeof(tree_node_t));
    if(node == NULL){
        return NULL;
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;

    return node;
}

void free_tree_node(tree_node_t *node){
    if(node == NULL){
        return;
    }
    node->left = NULL;
    node->right = NULL;
    free(node);
}

void swap(int *a, int *b){
    int c = *a;
    *a = *b;
    *b = c;
}

tree_node_t *up_filter(tree_node_t *root){
    if(root == NULL){
        return NULL;
    }
    if(root->left != NULL && root->right != NULL){
        if(root->data > root->left->data){
            swap(&root->data, &root->left->data);
        }
        if(root->data > root->right->data){
            swap(&root->data, &root->right->data);
        }
    }else if(root->left != NULL){
        if(root->data > root->left->data){
            swap(&root->data, &root->left->data);
        }
    }else if(root->right != NULL){
        if(root->data > root->right->data){
            swap(&root->data, &root->right->data);
        }
    }
    return root;
}

int get_balance_factor(tree_node_t *root){
    if(root->left != NULL && root->right != NULL){
        return root->left->height - root->right->height;
    }else if(root->left != NULL && root->right == NULL){
        return root->left->height;
    }else if(root->left == NULL && root->right != NULL){
        return 0 - root->right->height;
    }
    return 0;
}

void update_height(tree_node_t *root){
    if(root == NULL){
        return;
    }
    update_height(root->left);
    update_height(root->right);
    if(root->left != NULL && root->right != NULL){
        root->height = root->left->height < root->right->height ? root->left->height : root->right->height;
        root->height++;
    }else{
        root->height = 1;
    }
}

tree_node_t *sub_tree_insert_node(tree_node_t *root, int data){
    if(root == NULL){
        return new_tree_node(data);
    }
    int factor = get_balance_factor(root);
    if(factor <= 0){
        //插入左边
        //printf("to left\n");
        root->left = sub_tree_insert_node(root->left, data);
    }else{
        //插入右边
        //printf("to right\n");
        root->right = sub_tree_insert_node(root->right, data);
    }
    //printf("current node: %d\n", root->data);
    return up_filter(root);
}

void heap_sort_insert_node(tree_node_t **root, int data){
    if(root == NULL){
        return;
    }
    *root = sub_tree_insert_node(*root, data);
    update_height(*root);
}

tree_node_t *add_sub_tree_to_tree(tree_node_t *root, tree_node_t *sub){
    if(sub == NULL || root == NULL){
        return root;
    }
    add_sub_tree_to_tree(root, sub->left);
    add_sub_tree_to_tree(root, sub->right);
    return sub_tree_insert_node(root, sub->data);
}

int heap_sort_get_node(tree_node_t **root){
    if(root == NULL || *root == NULL){
        return INT_NAN;
    }
    tree_node_t *tree_root = *root;
    int data = tree_root->data;
    //printf("first node: %d\n", tree_root->data);
    if(tree_root->left == NULL && tree_root->right == NULL){
        free_tree_node(tree_root);
        *root = NULL;
    }else if(tree_root->left == NULL && tree_root->right != NULL){
        //右孩子非空，右孩子代替原结点
        *root = tree_root->right;
        free_tree_node(tree_root);
    }else if(tree_root->right == NULL && tree_root->left != NULL){
        //左孩子非空，左孩子代替原结点
        *root = tree_root->left;
        free_tree_node(tree_root);
    }else{
        //左右孩子非空
        tree_node_t *temp = NULL;
        tree_node_t *free_node = tree_root;
        if(tree_root->left->data < tree_root->right->data){
            //左孩子小于右孩子，左孩子代替原结点
            temp = tree_root->left->right;
            tree_root->left->right = tree_root->right;
            *root = tree_root->left;
        }else{
            //右孩子小于左孩子，右孩子代替原结点
            temp = tree_root->right->left;
            tree_root->right->left = tree_root->left;
            *root = tree_root->right;
        }
        free_tree_node(free_node);
        *root = add_sub_tree_to_tree(*root, temp);
        destroy_heap_tree(temp);
    }
    return data;
}

void destroy_heap_tree(tree_node_t *root){
    if(root == NULL){
        return;
    }
    destroy_heap_tree(root->left);
    destroy_heap_tree(root->right);
    free_tree_node(root);
}

void tree_print(tree_node_t *root){
    if(root == NULL){
        return;
    }
    printf("%d, ", root->data);
    tree_print(root->left);
    tree_print(root->right);
}
